class Solution {
public:
    int minDistance(string s1, string s2) {
        // dp[i][j]代表将他s1从0到i范围内的字符串变得和s2从0到j范围内的字符串一样需要最小操作次数为多少
        // 然后就是动态转移方程的书写了
        // 如果s1[i] == s2[j]
        // 那么此时的dp[i][j] = dp[i-1][j-1]
        // 如果s1[i]!=s2[j]
        // 此时存在三种方法插入删除和替换
        // dp[i][j] = min(dp[i][j-1](插入，就相当于在s1的末尾插入了一个s2末尾的元素，这样就将s2的最后一个元素去除了，)，
        //dp[i-1][j-1](将其中一个字符串的末尾字符替换成为了另外一个字符的最后一个字符),dp[i-1][j]删除了s1末尾的元素)+1
        int len1 = s1.size();
        int len2 = s2.size();
        s1 = "-"+s1;
        s2 = "-"+s2;
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
         // 初始化 dp 数组
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i; // 从 s1 转换到空字符串需要 i 次删除
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j; // 从空字符串转换到 s2 需要 j 次插入
        }

        for(int i = 1;i<=len1;i++)
        {
            for(int j = 1;j<=len2;j++)
            {
                if(s1[i] == s2[j])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
                }
            }
        }
        return dp[len1][len2];
    }
};